package gold.digger;

import gold.utils.InputUtil;

import java.util.Arrays;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC2188 {
    public long startExecuteTime = System.currentTimeMillis();


    /*
     * @param 此题目参考了别人代码
     * 不是因为复杂，而是因为经典
     * 这个题目反应了：思路远比代码重要，没有思路不要乱动手
     * @return:
     */
    class Solution {
        public int minimumFinishTime(int[][] tires, int changeTime, int numLaps) {
            //代表用一个轮胎，跑i圈，所用的最少时间
            int[] minSec = new int[18];
            //防止在计算跑i圈的最小值时，相加上溢出
            Arrays.fill(minSec, Integer.MAX_VALUE / 2);
            //枚举每一个轮胎，跑i圈的最小值
            for (int[] tire : tires) {
                long time = tire[0];

                //跑完第i圈，所用的时间，且最多跑numLaps圈
                //changeTime+tire[0]  跑一圈就换胎
                for (int i = 1, sum = 0; sum <= changeTime + tire[0] && i <= numLaps; i++) {
                    //不换胎，跑一圈
                    sum += time;
                    //所有轮胎中，跑完第i圈，所用的最少时间
                    minSec[i] = Math.min(minSec[i], sum);
                    //不换轮胎，跑完下一圈，所用的时间
                    time *= tire[1];
                }
            }
            int[] f = new int[numLaps + 1];
            Arrays.fill(f, Integer.MAX_VALUE);
            f[0] = 0;
            //跑i圈，所用的最少时间
            for (int i = 1; i <= numLaps; i++) {
                //先跑i-j圈，剩下的j圈，用一个轮胎跑完，所用的最少时间
                //一个轮胎，最多跑17圈
                for (int j = 1; j <= Math.min(17, i); j++)
                    f[i] = Math.min(f[i], f[i - j] + minSec[j]);
                //最后的i-j圈，由一个新的轮胎跑，所以中间有一个换胎过程
                f[i] += changeTime;
            }
            //减去刚开始的一次换胎过程
            return f[numLaps] - changeTime;
        }
    }

    class Solution_Wrong_Thought {
        public long minimumTime(int[] times, int totalTrips) {
            Arrays.sort(times);
            long left = 1, right = 1L * times[0] * totalTrips;// Math.max(((totalTrips * 1L * times[times.length - 1]) / times.length), times[0]);
            while (left < right) {
                long mid = (right - left) / 2 + left;
                if (curCanFinish(times, totalTrips, mid)) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }

            return right;
        }

        public boolean curCanFinish(int[] times, int totalTrips, long curTime) {
            int curTotal = 0;
            for (int time : times) {
                long curTri = curTime / time;
                curTotal += curTri;
                if (curTotal >= totalTrips) return true;
            }

            return false;
        }
    }

    public void run() {
        int[] arr = InputUtil.toIntegerArray("[1,2,3]");
        System.out.println(new Solution().toString());
    }

    public static void main(String[] args) throws Exception {
        LC2188 an = new LC2188();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
